/**
 * @description：求无序数组的第K大元素
 * @author: yangyahui01
 * @date: 12/27/24 3:20 PM
 */
public class 求无序数组的第K大元素 {

    public static void main(String[] args) {
        int[] nums = {6,1,3,8,2,4,9,4};

        int target = kthSmallest(nums, 7);
        System.out.println(target);

        print(nums);
    }

    public static int kthSmallest(int[] arr, int k) {
        if (arr == null || arr.length < k) {
            return -1;
        }

        int partition = partition(arr, 0, arr.length - 1);
        while (partition + 1 != k) {
            if (partition + 1 < k) {
                partition = partition(arr, partition + 1, arr.length - 1); //为啥去[p+1,n-1]查找，因为现在数组是从大到小排序的
            } else {
                partition = partition(arr, 0, partition - 1);
            }
        }

        return arr[partition];
    }

    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];

        int i = p;
        for (int j = p; j < r; j++) {
            if (arr[j] > pivot) {
                swap(arr, i, j);
                i++;
            }
        }

        swap(arr, i, r);

        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

}
